package q108_sortedArrayToBST;

import CommonClass.Common.TreeNode;

public class Solution {
    public static void main(String[] args) {

    }
    public TreeNode sortedArrayToBST(int[] nums) {
        return generateBST(nums, 0, nums.length - 1);
    }

    /**
     * 直接使用递归的方式来解决平衡搜索二叉树的问题
     * 首先二叉树是要满足左 < 根 < 右的 而nums已经排序结束了所以不需要重新进行排序
     * 那么高度差不大于1 实际上就是对于一个根节点，其左右两边树的深度，差值不能大于1（就是看左右两边有多少层）
     * 那么递归只需要每次把一个传入数组以及左右两个index，取出中间作为root节点，再将剩余左右节点的分别递归即可
     * @param nums
     * @param l
     * @param r
     * @return
     */
    private TreeNode generateBST(int[] nums, int l, int r) {
        if (r < l){
            return null;
        }
        TreeNode root = new TreeNode(nums[l + (r - l)/2]);
        root.left = generateBST(nums, l, l + (r - l)/2 - 1);
        root.right = generateBST(nums, l + (r - l)/2 + 1, r);
        return root;
    }
}
